package com.chenhao.springcloud.chenhaodatastructureservice.linkedlist;



/**
 * Description:虚拟头节点
 *
 * @author chenhao
 * @date 2020/12/9 11:09
 */
public class LinkedList<E> {
    private class Node{
        public E e;
        public Node next;

        public Node(E e,Node next){
            this.e= e;
            this.next = next;
        }
        public Node(E e){
            this(e,null);
        }
        public Node(){
            this(null,null);
        }
        @Override
        public String toString(){
            return e.toString();
        }

    }

    private Node dummyHead;
    private int size;

    public LinkedList(){
        dummyHead=new Node(null,null);
        size=0;
    }

    //获取链表中的元素
    public int getSize(){
        return size;
    }

    // 返回链表是否为空
    public boolean isEmpty(){
        return size==0;
    }
    //在链表头添加数据
    public void addFirst(E e){
        add(0,e);
    }
   //添加数据
    public void add(int index,E e){
        if (index<0 ||index>size){
            throw  new IllegalArgumentException("add failed.iLLegal index ");
        }
        Node prex = dummyHead;
        for (int i=0;i<index;i++) {
                prex = prex.next;
        }
        prex.next = new Node(e,prex.next);
        size++;

    }


    //在链表的尾部添加元素
    public void addLast(E e){
        add(size,e);
    }
    public E get(int index){
        if (index<0 ||index>size){
            throw  new IllegalArgumentException("add failed.iLLegal index ");
        }
        Node cur = dummyHead.next;
        for (int i=0;i<index;i++){
            cur= cur.next;
        }
        return cur.e;
    }

    public void set(int index,E e){
        if (index<0 ||index>size){
            throw  new IllegalArgumentException("add failed.iLLegal index ");
        }
        Node cur =dummyHead.next;
        for (int i=0;i<index;i++){
            cur=cur.next;
        }
        cur.e = e;
    }

   //是否包含
    public boolean contains(E e){
        Node cur =dummyHead.next;
        while (cur!=null){
            if (cur.e.equals(e)){
                return true;
            }
            cur= cur.next;
        }
        return false;
    }
    //重写toString方法
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        Node cur = dummyHead.next;
        while (cur!=null){
            res.append(cur+"->");
            cur= cur.next;
        }
        res.append("NULL");
        return res.toString();
    }

    public E remove(int index){
        if (index<0 ||index>size){
            throw  new IllegalArgumentException("add failed.iLLegal index ");
        }
        Node prev = dummyHead;
        for (int i=0;i<index;i++){
            prev = prev.next;
        }

        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next= null;
        size--;

        return retNode.e;
    }


}
